The term “three-dimensional pattern nesting” refers to the process of arranging multiple three-dimensional objects in an optimized or near-optimized configuration so as to occupy the least amount of total space in a bounded region and to minimize associated costs and risks. Two-dimensional pattern nesting of planar objects has been studied extensively due to the significant interest of many industries in which efficient utilization of materials from which parts are fabricated is highly desired; for instance, the garment industry, the sheet metal industry, and the auto industry. As is apparent, a single extra percent of material utilization can result in a large amount of total dollar savings where parts are to be mass produced.
Problems complicating two-dimensional pattern nesting in these industries have been considered. For instance, in the sheet metal, steel and garment industries, predetermined part shapes are typically cut from one or more layers of material (e.g. sheet metal, steel, cloth, leather, etc.) having a rectangular shape of fixed width. However, due to directional properties of the materials (for example, the warp and weave of textiles) from which the part shapes are to be cut, the part shapes can only be arranged along relatively few of a plurality of possible rotational orientations. See, for example, U.S. Pat. No. 5,815,398 (September 1998).
In the semiconductor industry, the specific problems facing the production of mask patterns for circuit integration have also been considered. Here, the problem is the dissection of rectangles into smaller rectangles where the usefulness and the quality of the dissection depend on the position of the rectangles relative to each other and to the enveloping rectangle. See, for example, U.S. Pat. No. 4,554,625 (November 1985).
Also previously considered is two-dimensional pattern nesting in the context of stock-cutting. In particular, stock-cutting in which a machine is capable of dissecting rectangular sheets up to a certain size by a cut parallel to one of the sides and all the way across the sheet has been considered. See, for example, U.S. Pat. No. 4,554,625 (November 1985).
Application of three-dimensional pattern nesting to the order fulfillment and shipping industry (affectionately called the “pick, pack and ship” or “PPS” industry) presents a unique and especially difficult problem. Unlike in the traditional industries in which two-dimensional pattern nesting algorithms have been extensively studied and applied, optimization of materials utilization has not been widely recognized as a viable goal in the PPS industry. This is due in part to the existence of various, often competing, cost-related constraints.
Existing automation packages tailored to the PPS industry, for example the Delfour Warehouse Management System™ package, provide automated warehouse administration services for areas such as inventory management, route planning, order picking and billing/invoicing, but do not provide optimization of order picking, packing and shipping. Additionally, existing systems are insufficient to accommodate the complexity of real-world needs of the PPS industry.
What is needed is an effective method and system for optimization of the costs associated with order fulfillment in the PPS industry. Specifically, a method of optimized sequencing and configuring of items to be picked, packed and shipped is needed.